#include<iostream>
//相当于选择排序，只不过选择用了最大堆的数据结构，根就是最大值。
//构建一个堆
void MakeHeap(int *a,int n,int index)//以index为根构建最大堆
{
    int left=2*index+1;
    int right=2*index+2;
    int max=index;
    if(left<n&&a[left]>a[max])
    {
        max=left;
    }
    if(right<n&&a[right]>a[max])
    {
        max=right;
    }
    if(max!=index)
    {
        std::swap(a[max],a[index]);
        MakeHeap(a,n,max);
    }
}
void HeapSort(int *a,int n)
{
    //先有数列在有数据结构是反向构建
    //先有数据结构在有数列是从前往后插入
    //从数列最后一个数开始和后面的孩子一起构建最大堆
    for(int i=n/2-1;i>=0;i--)//从第一个非叶子结点（n/2-1）开始构建最大堆
    {
        MakeHeap(a,n,i);
    }
    for(int i=n-1;i>0;i--)
    {
        std::swap(a[0],a[i]);//把最大值放最后面
        MakeHeap(a,i,0);
    }

}


int main()
{
    int a[5]={5,1,2,6,3};
    HeapSort(a,5);
    for(int i=0;i<5;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;




    return 0;
}